//Given an array of points where points[i] = [xi, yi] represents a point on the 
//X-Y plane, return the maximum number of points that lie on the same straight lin
//e. 
//
// 
// Example 1: 
//
// 
//Input: points = [[1,1],[2,2],[3,3]]
//Output: 3
// 
//
// Example 2: 
//
// 
//Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
//Output: 4
// 
//
// 
// Constraints: 
//
// 
// 1 <= points.length <= 300 
// points[i].length == 2 
// -104 <= xi, yi <= 104 
// All the points are unique. 
// 
// Related Topics 哈希表 数学 
// 👍 246 👎 0

package leetcode.editor.cn;

import javafx.util.Pair;

import java.util.HashMap;
 class P149MaxPointsOnALine {
    public static void main(String[] args) {
        Solution solution = new P149MaxPointsOnALine().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        int[][] points;
        int n;
        HashMap<Double, Integer> lines = new HashMap<Double, Integer>();
        int horisontal_lines;

        public Pair<Integer, Integer> add_line(int i, int j, int count, int duplicates) {
    /*
    Add a line passing through i and j points.
    Update max number of points on a line containing point i.
    Update a number of duplicates of i point.
    */
            // rewrite points as coordinates
            int x1 = points[i][0];
            int y1 = points[i][1];
            int x2 = points[j][0];
            int y2 = points[j][1];
            // add a duplicate point
            if ((x1 == x2) && (y1 == y2))
                duplicates++;
                // add a horisontal line : y = const
            else if (y1 == y2) {
                horisontal_lines += 1;
                count = Math.max(horisontal_lines, count);
            }
            // add a line : x = slope * y + c
            // only slope is needed for a hash-map
            // since we always start from the same point
            else {
                double slope = 1.0 * (x1 - x2) / (y1 - y2) + 0.0;
                lines.put(slope, lines.getOrDefault(slope, 1) + 1);
                count = Math.max(lines.get(slope), count);
            }
            return new Pair(count, duplicates);
        }

        public int max_points_on_a_line_containing_point_i(int i) {
    /*
    Compute the max number of points
    for a line containing point i.
    */
            // init lines passing through point i
            lines.clear();
            horisontal_lines = 1;
            // One starts with just one point on a line : point i.
            int count = 1;
            // There is no duplicates of a point i so far.
            int duplicates = 0;

            // Compute lines passing through point i (fixed)
            // and point j (interation).
            // Update in a loop the number of points on a line
            // and the number of duplicates of point i.
            for (int j = i + 1; j < n; j++) {
                Pair<Integer, Integer> p = add_line(i, j, count, duplicates);
                count = p.getKey();
                duplicates = p.getValue();
            }
            return count + duplicates;
        }


        public int maxPoints(int[][] points) {

            this.points = points;
            // If the number of points is less than 3
            // they are all on the same line.
            n = points.length;
            if (n < 3)
                return n;

            int max_count = 1;
            // Compute in a loop a max number of points
            // on a line containing point i.
            for (int i = 0; i < n - 1; i++)
                max_count = Math.max(max_points_on_a_line_containing_point_i(i), max_count);
            return max_count;
        }



//        int maxPoints(int[][] points) {
//            if (points.length < 3) {
//                return points.length;
//            }
//            int num_points = points.length;
//            int res = 1;
//            for (int i = 0; i < num_points; ++i) {
//                // 记录除了当前i点之外，每个点的斜率
//                HashMap<Double, Integer> record = new HashMap<Double, Integer>();
//                // 记录相同点的个数
//                int same_point = 0;
//                for (int j = 0; j < num_points; ++j) {
//                    // 跳过当前i点
//                    if (j == i) {
//                        continue;
//                    }
//                    // 记录相同点
//                    if (points[i] == points[j]) {
//                        ++same_point;
//                        continue;
//                    }
//                    // 记录斜率无穷大的点
//                    if (points[i][1] == points[j][1]) {
//                        ++record[DBL_MAX];
//                        continue;
//                    }
//                    // 记录斜率为0的点
//                    if (points[i][0] == points[j][0]) {
//                        ++record[0];
//                        continue;
//                    }
//                    // 记录其他斜率的点
//                    double slope = (double)(points[i][1] - points[j][1])
//                            / (double)(points[i][0] - points[j][0]);
//                    ++record[slope];
//                }
//                // 获得i点中，相同斜率的最大点数
//                int cur_max = INT_MIN;
//                for (auto it : record) {
//                    cur_max = max(cur_max, it.second);
//                }
//                // 与全局res作比较，需要注意的是当前i的最大点数需要***加上i点本身和相同的点数***
//                res = max(res, same_point + cur_max + 1);
//            }
//            return res;
//
}
//leetcode submit region end(Prohibit modification and deletion)

}